/**
 * 
 */
package dp.passed;

import java.util.Stack;

/**
 * @author xyyi
 *
 */
public class LargestRectangleinHistogram {

	/**
	Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
	Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
	The largest rectangle is shown in the shaded area, which has area = 10 unit.

	For example,
	Given height = [2,1,5,6,2,3],
	return 10.
	 */
	// 2 scans, time O(n) space O(n)
	public int largestRectangleArea(int[] height) {
		if (height == null || height.length == 0)
			return 0;

		int[] lefts = new int[height.length];
		Stack<Integer> stack = new Stack<Integer>();
		for (int i = 0; i < height.length; i++) {
			while (!stack.isEmpty()) {
				if (height[stack.peek()] < height[i]) {
					break;
				} else {
					stack.pop();
				}
			}
			if (stack.isEmpty()) {
				lefts[i] = 0;
			} else {
				lefts[i] = stack.peek() + 1;
			}
			stack.push(i);
		}

		stack.clear();
		int max = 0;
		for (int i = height.length - 1; i >= 0; i--) {
			while (!stack.isEmpty()) {
				if (height[stack.peek()] < height[i]) {
					break;
				} else {
					stack.pop();
				}
			}

			int right = 0;
			int area = 0;
			if (stack.isEmpty()) {
				right = height.length - 1;
			} else {
				right = stack.peek() - 1;
			}
			stack.push(i);

			area = height[i] * (right - lefts[i] + 1);
			max = Math.max(max, area);
		}

		return max;
	}

	// 1 scan
	public int largestRectangleArea1Scan(int[] heights) {
		if (heights == null || heights.length == 0)
			return 0;

		int[] heightArr = new int[heights.length + 1];
		for (int i = 0; i < heights.length; i++)
			heightArr[i] = heights[i];
		heightArr[heightArr.length - 1] = -1;

		int maxArea = 0;
		Stack<Integer> stack = new Stack<Integer>();
		int height = 0;
		for (int i = 0; i < heightArr.length; i++) {
			if (heightArr[i] < height) {
				while (heightArr[i] <= height) {
					stack.pop();

					int index = stack.isEmpty() ? -1 : stack.peek();
					int area = (i - index - 1) * height;
					maxArea = area > maxArea ? area : maxArea;

					if (stack.isEmpty())
						break;

					height = heightArr[index];
				}
			}
			height = heightArr[i];
			stack.push(i);
		}

		return maxArea;
	}

	// Best solution
	int largestRectangleArea1ScanBest(int[] heights) {
		int[] h = new int[heights.length + 1];
		for (int i = 0; i < heights.length; i++)
			h[i] = heights[i];
		h[h.length - 1] = 0; // add the 0 to the heights array 

		Stack<Integer> stack = new Stack<Integer>();
		int i = 0, max = 0;
		while (i < h.length) {
			if (stack.empty() || h[stack.peek()] <= h[i])
				stack.push(i++);
			else {
				int index = stack.pop();
				max = Math.max(max,
						h[index] * (stack.empty() ? i : i - stack.peek() - 1));
			}
		}
		return max;
	}

	/**
	 * 
	 */
	public LargestRectangleinHistogram() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LargestRectangleinHistogram lrh = new LargestRectangleinHistogram();
		int[] heights = { 4, 2, 0, 3, 2, 5 };
		System.out.println(lrh.largestRectangleArea1ScanBest(heights));

	}

}
